package 数据结构.排序.实例;
/**
 * 归并排序就是先把原来的数据进行分割（一直分割到每个里面只有一个数据），然后对于每一个分割完的左右子序列进行排序，将排序后的结果放入到原来的数组
 * 从而做到暂时的有序，然后经过不断的递归，最后回溯到最开始的数组大小，再经过一次的排序就完成了归并排序的全过程。
 *
 * 当有n个记录的时候，需要进行log以2为底n趟归并排序，每一趟归并其关键字比较次数都不超过N，元素移动的次数都是n，因此归并排序的时间复杂度为O(nlog2n)
 * 空间复杂度使用顺序表实现时，需要和待排序的数组相同大小的辅助数组，因此空间复杂度为O(n)
 * 算法是稳定排序
 * 可用于链式结构，且不需要附加存储空，但是递归实现时仍需要开辟相应的递归工作栈
 * */
public class $06_归并排序 {

    public static void Msort(int []a,int []b,int lo,int hi){//a[lo...hi]归并排序后放入到b[lo..hi]中
        if(lo==hi)
            b[lo]=a[lo];
        else
        {
            int mid=(lo+hi)/2;//将当前序列一分为二，求出分裂点mid
            Msort(a,b,lo,mid);//对子序列数组a的lo..mid递归归并排序，结果放入到数组b中lo..mid
            Msort(a,b,mid+1,hi);//对子序列数组a的mid+1..hi递归归并排序，结果放入到数组b中mid+1..hi
            merge(a,b,lo,mid,hi);//将数组b[lo..mid]和b[mid+1..hi]归并到a[lo..hi]
        }
    }

    static void merge(int[] a, int[] b, int lo, int mid, int hi){//将两边的数据排序到一个数组中

        int i=lo;int j=mid+1;int k=lo;
        while (j<=hi&&i<=mid){//将数组a中的数据从小到大的并入到辅助数组b中
            if(a[i]<a[j])
                b[k++]=a[i++];
            else
                b[k++]=a[j++];
        }
        while (i<=mid)//将剩余的a中lo到mid的数据加入到数组b中
            b[k++]=a[i++];
        while (j<=hi)//将剩余的a中的mid+1到hi的数据加入到数组b中
            b[k++]=a[j++];
        while (lo<=hi){
            a[lo]=b[lo];
        lo++;
        }
    }



}
